﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MatrixGraphDijkstra
{
	public class Program
	{
		static void Main(string[] args)
		{
			MatrixGraphManager manager = new MatrixGraphManager();
            //创建图
            MatrixGraph graph = manager.CreateMatrixGraph();
            manager.OutMatrix(graph);
            int sum = 0;
            manager.Prim(graph, out sum);
            Console.WriteLine("\n最小生成树的权值为：" + sum);
            manager.Dijkstra(graph);
            Console.ReadLine();
		}
	}

	#region 邻接矩阵的结构图

	public class MatrixGraph
	{
		//保存定点的信息
		public string[] vertex;
		//保存边信息
		public int[,] edges;
		//深搜和广搜的遍历标志
		public bool[] isTrav;
		//顶点数量
		public int vertexNum;
		//边数量
		public int edgeNum;
		//图类型
		public int graphType;

		/// <summary>
		/// 存储容量的初始化
		/// </summary>
		/// <param name="vertexNum"></param>
		/// <param name="edgeNum"></param>
		/// <param name="graphType"></param>
		public MatrixGraph(int vertexNum, int edgeNum, int graphType)
		{
			this.vertexNum = vertexNum;
			this.edgeNum = edgeNum;
			this.graphType = graphType;

			vertex = new string[vertexNum];
			edges = new int[vertexNum, edgeNum];
			isTrav = new bool[vertexNum];
		}
	}

	#endregion

	#region 图的操作类

	public class MatrixGraphManager
	{
		#region 图的创建
		
		public MatrixGraph CreateMatrixGraph()
		{
			Console.WriteLine("请输入创建图的顶点个数，边个数，是否为无向图(0,1来表示)，已逗号隔开。");
			var initData = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();
			MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);
			//我们默认“正无穷大为没有边”
            for (int i = 0; i < graph.vertexNum; i++)
            {
                for (int j = 0; j < graph.vertexNum; j++)
                {
                    graph.edges[i, j] = short.MaxValue;
                }
            }
			Console.WriteLine("请输入各顶点信息：");
			for (int i = 0; i < graph.vertexNum; i++)
			{
				Console.Write("\n第" + (i + 1) + "个顶点为:");
				var single = Console.ReadLine();
				//顶点信息加入集合中
				graph.vertex[i] = single;
			}
			Console.WriteLine("\n请输入构成两个顶点的边和权值，以逗号隔开。\n");
			for (int i = 0; i < graph.edgeNum; i++)
			{
				Console.Write("第" + (i + 1) + "条边:\t");
				initData = Console.ReadLine().Split(',').Select(j => int.Parse(j)).ToList();
				int start = initData[0];
				int end = initData[1];
				int weight = initData[2];
				//给矩阵指定坐标位置赋值
				graph.edges[start - 1, end - 1] = weight;
				//如果是无向图，则数据呈“二，四”象限对称
				if (graph.graphType == 1)
				{
					graph.edges[end - 1, start - 1] = weight;
				}
			}
			return graph;
		}

		#endregion

		#region 输出矩阵数据
		/// <summary>
		/// 输出矩阵数据
		/// </summary>
		/// <param name="graph"></param>
		public void OutMatrix(MatrixGraph graph)
		{
			for (int i = 0; i < graph.vertexNum; i++)
			{
				for (int j = 0; j < graph.vertexNum; j++)
				{
					 if (graph.edges[i, j] == short.MaxValue)
                         Console.Write("∽\t");
                     else
                         Console.Write(graph.edges[i, j] + "\t");
				}
				//换行
				Console.WriteLine();
			}
		}

		#endregion

		#region prim算法获取最小生成树

		/// <summary>
		/// prim算法获取最小生成树
		/// </summary>
		/// <param name="graph"></param>
         public void Prim(MatrixGraph graph, out int sum)
         {
             //已访问过的标志
             int used = 0;
             //非邻接顶点标志
             int noadj = -1;
             //定义一个输出总权值的变量
             sum = 0;
             //临时数组，用于保存邻接点的权值
             int[] weight = new int[graph.vertexNum];
             //临时数组，用于保存顶点信息
             int[] tempvertex = new int[graph.vertexNum];
             //取出邻接矩阵的第一行数据，也就是取出第一个顶点并将权和边信息保存于临时数据中
             for (int i = 1; i < graph.vertexNum; i++)
             {
                 //保存于邻接点之间的权值
                 weight[i] = graph.edges[0, i];
                 //等于0则说明V1与该邻接点没有边
                 if (weight[i] == short.MaxValue)
                     tempvertex[i] = noadj;
                 else
                     tempvertex[i] = int.Parse(graph.vertex[0]);
             }
 
             //从集合V中取出V1节点，只需要将此节点设置为已访问过，weight为0集合
             var index = tempvertex[0] = used;
             var min = weight[0] = short.MaxValue;
             //在V的邻接点中找权值最小的节点
             for (int i = 1; i < graph.vertexNum; i++)
             {
                 index = i;
                 min = short.MaxValue;
                 for (int j = 1; j < graph.vertexNum; j++)
                 {
                     //用于找出当前节点的邻接点中权值最小的未访问点
                     if (weight[j] < min && tempvertex[j] != 0)
                     {
                         min = weight[j];
                         index = j;
                     }
                 }
                 //累加权值
                 sum += min;
                 Console.Write("({0},{1})  ", tempvertex[index], graph.vertex[index]);
                 //将取得的最小节点标识为已访问
                 weight[index] = short.MaxValue;
                 tempvertex[index] = 0;
                 //从最新的节点出发，将此节点的weight比较赋值
                 for (int j = 0; j < graph.vertexNum; j++)
                 {
                     //已当前节点为出发点，重新选择最小边
                     if (graph.edges[index, j] < weight[j] && tempvertex[j] != used)
                     {
                         weight[j] = graph.edges[index, j];
                         //这里做的目的将较短的边覆盖点上一个节点的邻接点中的较长的边
                         tempvertex[j] = int.Parse(graph.vertex[index]);
                     }
                 }
             }
         }

         #endregion

		#region dijkstra求出最短路径
		/// <summary>
		/// dijkstra求出最短路径
		/// </summary>
		/// <param name="g"></param>
        public void Dijkstra(MatrixGraph g)
        {
            int[] weight = new int[g.vertexNum];
            int[] path = new int[g.vertexNum];
            int[] tempvertex = new int[g.vertexNum];
            Console.WriteLine("\n请输入源点的编号：");
            //让用户输入要遍历的起始点
            int vertex = int.Parse(Console.ReadLine()) - 1;
            for (int i = 0; i < g.vertexNum; i++)
            {
                //初始赋权值
                weight[i] = g.edges[vertex, i];
                if (weight[i] < short.MaxValue && weight[i] > 0)
                    path[i] = vertex;
                tempvertex[i] = 0;
            }
            tempvertex[vertex] = 1;
            weight[vertex] = 0;
            for (int i = 0; i < g.vertexNum; i++)
            {
                int min = short.MaxValue;
                int index = vertex;
                for (int j = 0; j < g.vertexNum; j++)
                {
                    //顶点的权值中找出最小的
                    if (tempvertex[j] == 0 && weight[j] < min)
                    {
                        min = weight[j];
                        index = j;
                    }
                }
                tempvertex[index] = 1;
                //以当前的index作为中间点，找出最小的权值
                for (int j = 0; j < g.vertexNum; j++)
                {
                    if (tempvertex[j] == 0 && weight[index] + g.edges[index, j] < weight[j])
                    {
                        weight[j] = weight[index] + g.edges[index, j];
                        path[j] = index;
                    }
                }
            }
            Console.WriteLine("\n顶点{0}到各顶点的最短路径为：（终点 < 源点） " + g.vertex[vertex]);
            //最后输出
            for (int i = 0; i < g.vertexNum; i++)
            {
                if (tempvertex[i] == 1)
                {
                    var index = i;
                    while (index != vertex)
                    {
                        var j = index;
                        Console.Write("{0} < ", g.vertex[index]);
                        index = path[index];
                    }
                    Console.WriteLine("{0}\n", g.vertex[index]);
				}
                else
                {
                    Console.WriteLine("{0} <- {1}: 无路径\n", g.vertex[i], g.vertex[vertex]);
                }
			}
         }
         #endregion
	}

	#endregion
}
